Communication networks typically include stations, known as nodes, connected by links. Nodes may be connected via links on a point-to-point basis, e.g., via serial lines or via a shared media of some type, e.g., Ethernet, shared radio or cellular channels. Data is transmitted from node to node across the links via paths as determined by the routing mechanism. Routing and can be done at a central location or distributed to a number of locations in the network.
Shortest path algorithms (SPA) are a well-known technique for determining the most efficient communication routes. For example, Dijkstra's shortest path algorithm is used in OSPF-2 and the Bellman-Ford algorithm is used in the BGP-4 routing technique and in a quality-of-service (QoS) routing method (U.S. Pat. No. 5,233,604). In distributed routing approaches, nodes that participate in routing are called ‘routers’, but this does not preclude that node from also acting as a messaging source or destination. In many cases, routing is distributed so that each node determines the next hop for a transmission based on the destination address. Several extensions to this basic operation are known, including: a priori selection of a routing path based on a requested QoS level (U.S. Pat. No. 6,134,589); per packet routing based on a QoS specification contained within the packet (U.S. Pat. No. 6,091,709); routing based on source address as well as destination (U.S. Pat. No. 6,091,725); use of information within the packet, rather than the destination address, to access distinct secondary routing tables/information (U.S. Pat. No. 5,353,283); admission control or incoming rate control of messaging requests to avoid network congestion (U.S. Pat. Nos. 5,367,523, 5,400,329, 6,038,216) (sometimes using ‘back-pressure’ or ‘reverse-flow’ techniques); routing based on geographical, rather than network topological, features (U.S. Pat. Nos. 4,939,726, 6,130,890); centralized control and distribution of routing information (U.S. Pat. No. 5,987,521); QoS bandwidth guarantees under a single link failure using a backup route; as well as others.
Although most routing techniques determine a communication path based on the optimization of some metric (network specification such as the number of nodes [hops] visited along the route, delay, cost, etc.), QoS-oriented methods are geared towards techniques for finding and maintaining routes so that one or more metrics are kept to a minimum along a complete end-to-end path (such as bandwidth, jitter, delay, etc.).
Normal routing usually considers additive properties of some metric (like number of hops, link delay, cost) to find shortest routes. While the latter often uses a form of shortest path algorithm, the algorithms used in QoS problems are sometimes called ‘restricted’ or ‘constrained’ shortest path methods or use flow-based techniques. The term ‘flow’ arises as one can view the packets transmitted within the network in association with a communication session from point to point as a ‘flow’. Problems associated with the QoS routing of multiple simultaneous network flows where each is categorized as belonging to some class are sometimes referred to as ‘multi-commodity flow’ problems. For example, each TCP session might be considered a flow and each might have an assigned classification or level of expected service.
A variety of techniques are available to determine the necessary metrics for proper routing. The term ‘link-state’ is commonly used to refer to the status of any number of possible metrics (such as packet loss rate, bandwidth, latency, cost of use, current utilization rate, etc.) of the direct interconnections between or among nodes. Alternatively, nodes may share/exchange routing table information (e.g. assigned metrics, number of hops, etc.) regarding the reachability (availability) of other nodes known to them. In order for overall network routing to occur, the inter-node (e.g., router) sharing of link states or reachability on a periodic basis or when a significant change in network status occurs is used. Such messages are usually called ‘route-updates’ or ‘link-state advertisements.’ Some extensions or alternative approaches have been proposed, including: explicit centralized control of link-state testing at each remote router (U.S. Pat. No. 5,881,051); congestion or packet loss detection with report to source (U.S. Pat. No. 5,090,011); use of time stamps on one-way or round-trip packet traffic for delay measurement (U.S. Pat. No. 5,563,875); as well as others.
Routing techniques mostly based on link-state exchange (e.g., U.S. Pat. No. 4,644,532) are often referred to as link-state methods while those that exchange routing tables are often called distance-vector methods. In either case, the process of achieving agreed upon routing such that all routers in the network use the latest information is called ‘convergence.’ As discussed above, convergence may be reached via the periodic or asynchronous exchange of link-state, distance-vector or other routing information among network routers. The state of network convergence may be disturbed by resource (e.g. communication links or computer hardware/software) failures, bringing a new resource into the network, dropping a resource from the network, or other changes of system state.
Prior to convergence, or between periods of convergence, a condition of misdirection or ‘routing loops’ may exist since some network components may not have accurate network state information. Even when operating under convergence ‘as normal’, network routes may not be using optimal paths for data transfers. For example, a recent study of the Internet has found that significantly better routing existed for 10–60% of end-to-end routes examined.
The prime objective of communication networks, such as the Internet, is delivery of data despite various network resources becoming intermittently overloaded or unavailable. Recent measurements show that fast wide-area routing convergence remains elusive for a variety of reasons; as has been shown, broad network convergence after a link or node failure (versus their return to service) may require from tens of seconds to tens of minutes. Furthermore links or nodes may become sporadically overloaded or congested in such ‘best-effort’ networks. Obviously, such behavior has a severely detrimental effect on both on-going as well as any attempted newly-initiated communications.